package org.gzc.sort;

import java.util.Arrays;

/**
 * @Description: 堆排序
 * @Author: guozongchao
 * @Date: 2020/8/15 14:04
 */
public class HeapSort implements SortStrategy{

    private class Node{
         int value;
         Node left;
         Node right;

        public Node(int value) {
            this.value=value;
        }
    }

    @Override
    public void sort(int[] array) {
        //首先将一个无序序列调整为一个 大顶堆
        //从最后一个非叶子结点开始进行局部调整,自下而上，自左而右进行
        //最后一个非叶子结点在序列中的索引为 i = length/2-1 (序列从0开始)
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjust(array,i,array.length);
        }
//        System.out.println(Arrays.toString(array));

        //得到大顶堆后，堆顶结点 即为 最大值
        //将堆顶元素与 最后元素交换，即在序列中 第一个元素 和 最后一个元素 交换
        //重新调整 堆结构
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[i];
            array[i]=array[0];
            array[0]=temp;
            adjust(array,0,i);
        }
//        System.out.println(Arrays.toString(array));
    }

    /**
     * 调整一个堆,使其成为大顶堆
     * @param array  数组序列
     * @param index  需要调整的堆的根结点在序列中对应的下标索引值
     * @param length 序列的长度
     */
    public void adjust(int[] array, int index, int length) {

        //保存当前结点值
        int temp = array[index];
        //开始调整，从当前结点的左结点开始
        for (int i = 2 * index + 1; i < length; i = 2 * i + 1) {
            //如果右结点存在 并且 右结点比左结点值大
            if (i + 1 < length && array[i] < array[i + 1]) {
                //i 指向右结点
                i++;
            }
            //如果 右子结点值比 父节点的值 大
            if (array[i] > temp) {
                //将右子结点往上提，即赋值给父节点（父节点已经临时保存在temp中）
                array[index]=array[i];
                //将i赋值给index
                //将当前右子结点 作为 父结点 继续进行调整
                index=i;
            }else{
                break;
            }
        }
        //当 for 循环结束后，我们已经将以index为父结点的树的最大值，放在了 最顶(局部)
        array[index]=temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        heapSort.sort(new int[]{4,6,8,5,12,9});
    }
}
